package com.mashibing.class13;

import java.util.ArrayList;
import java.util.List;

/**
 *派对的最大快乐值
 *  公司的每个员工都符合 Employee 类的描述。
 *  整个公司的人员结构可以看作是一棵标准的、 没有环的多叉树。
 *  树的头节点是公司唯一的老板。
 *  除老板之外的每个员工都有唯一的直接上级。
 *  叶节点是没有任何下属的基层员工(subordinates列表为空)，除基层员工外，每个员工都有一个或多个直接下级。
 *
 *  老板 , 老板手下有几个副总经理,
 *  一个员工手下拥有4个下级, 一个员工只有一个上级
 *  类似员工的多叉树
 *  1)原则 选节点
 *  2)选择了当前节点的话, 它的父节点和自己点就不能再选了.
 *
 *  派对的最大快乐值
 * 这个公司现在要办party，你可以决定哪些员工来，哪些员工不来，规则：
 * 1.如果某个员工来了，那么这个员工的所有直接下级都不能来
 * 2.派对的整体快乐值是所有到场员工快乐值的累加
 * 3.你的目标是让派对的整体快乐值尽量大
 * 给定一棵多叉树的头节点boss，请返回派对的最大快乐值。
 */
public class Code04_MaxHappy {
    public static class Employee {
        public int happy;
        public List<Employee> nexts;

        public Employee(int h) {
            happy = h;
            nexts = new ArrayList<>();
        }
    }

    public static class Info{
        public int no;
        public int yes;

        public Info(int no, int yes) {
            this.no = no;
            this.yes = yes;
        }
    }

    public static int maxHappy(Employee head) {
        if (head == null) {
            return 0;
        }
        Info allInfo = process(head);
        return Math.max(allInfo.yes, allInfo.no);
    }

    private static Info process(Employee employee) {
        if (employee==null){
            return new Info(0,0);
        }
        int no = 0;
        int yes = employee.happy;
        for (Employee next : employee.nexts) {
            Info nextInfo = process(next);
            no += Math.max(nextInfo.yes, nextInfo.no);
            yes += nextInfo.no;
        }
        return new Info(no,yes);
    }
}
